package LeetCode;

import java.util.*;

//
// Created by ✎﹏ℳ๓独赏☆独醉 on 2024/4/28.
// 
public class 电话号码的字母组合 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        List<String> res =letterCombinations(scan.next());
        System.out.println(res);
    }
    public static List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if(digits.equals(""))return res;
        HashMap<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        char[][] arr = new char[digits.length()][];
        for (int i = 0; i < digits.length(); i++) {
            String str = map.get(digits.charAt(i));
            arr[i] = str.toCharArray();
        }
//        System.out.println(Arrays.deepToString(arr));
        return dfs(arr,res,0, "");
    }

    private static List<String> dfs(char[][] arr, List<String> res, int line, String temp) {
        if(line == arr.length){
            res.add(temp);
        }else {
            for (int column = 0; column < arr[line].length; column++) {
                temp = temp + arr[line][column];
                dfs(arr,res,line+1, temp);
                temp = temp.substring(0,line);
            }
        }
        return res;
    }
}
